# 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中B[i] 的值是数组 A 中除了下标 i 以外的元素的积,
# 即B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
#
# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof

# 输入: [1,2,3,4,5]
# 输出: [120,60,40,30,24]


class Solution:
    def constructArr(self, a):
        n = len(a)
        res, tmp = [1] * n, 1
        for i in range(1, n):
            tmp *= a[i - 1]
            res[i] *= tmp
        tmp = 1
        for i in range(n-2, -1, -1):
            tmp *= a[i+1]
            res[i] *= tmp
        return res


# 使用除法了，不行
class Solution1:
    def constructArr(self, a):
        multi = 1
        num_0 = 0
        for num in a:
            if num == 0:
                num_0 += 1
            else:
                multi *= num
        if num_0 == 0:
            return [multi//i for i in a]
        elif num_0 == 1:
            return [multi if i == 0 else 0 for i in a]
        else:
            return [0] * len(a)

s = Solution()
s.constructArr([1,2,3,4,5])